package algorithm.poj.p3000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.Arrays;
import java.util.StringTokenizer;


/**
 * 分析：
 * 典型的差分约束系统，只要找到一组解，输出解的最大差距就可以。
 * 一般的差分约束系统使用Bellman-Ford算法，算法复杂度是O(EV)，
 * 但这里所有边都是非负数，可以使用Dijkstra算法，复杂度是O(V^2 + E)。
 *  
 * 实现：
 * 经验：
 * 教训：
 * 
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P3159 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P3159.class.getResource("P3159.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		String line = stdin.readLine();
		StringTokenizer st = new StringTokenizer(line);
		int N = Integer.valueOf(st.nextToken());
		int M = Integer.valueOf(st.nextToken());
		Edge[] edges = new Edge[M+N];
		for (int i = 0; i < N; i ++) {
			edges[i] = new Edge();
			edges[i].v = i+1;
			edges[i].u = 0;
			edges[i].w = 0;
		}
		for (int i = 0; i < M; i ++) {
			line = stdin.readLine();
			st = new StringTokenizer(line);
			edges[i+N] = new Edge();
			edges[i+N].v = Integer.valueOf(st.nextToken());
			edges[i+N].u = Integer.valueOf(st.nextToken());
			edges[i+N].w = Integer.valueOf(st.nextToken());
		}
		
		int[] d = new int[N+1];
		d[0] = 0;
		for (int i = 1; i < d.length; i ++) {
			d[i] = Integer.MAX_VALUE;
		}
		for (int i = 0; i <= N; i ++) {
			for (int j = 0; j < edges.length; j ++) {
				Edge e = edges[j];
				if (d[e.v] > d[e.u] + e.w) {
					d[e.v] = d[e.u] + e.w;
				}
			}
		}
		Arrays.sort(d);
		for (int i = 1; i < d.length; i ++) {
			System.out.println(d[i]);
		}
		System.out.println("----------------------");
		System.out.println(d[N]-d[1]);
	}
	
	private static class Edge {
		int u;
		int v;
		int w;
	}
}